#pragma once
#include "mytypes.h"

namespace poly
{
	class QuadTree
	{
	public:
		class Node;

		// nested classes/structs
		struct Span
		{
			float xmin, xmax;
			float ymin, ymax;
		};

		// leaf objects in the tree
		class IObject
		{
		public:
			IObject();

			virtual Span span() const = 0;
			virtual bool isStatic() const = 0;
			Node* node;
		};

		// represents an area, partitioned into four areas
		class Node
		{
		public:
			typedef std::set<IObject*> ObjectSet;

			Node( float xmin, float xmax, float ymin, float ymax );

			void insert( IObject *, int capacity );

			// members
			float xmin, xmax;
			float ymin, ymax;

			Node
				*left_top,
				*left_bottom,
				*right_top,
				*right_bottom;

			Node *parent;

			ObjectSet objects;

		private:
			void insertIntoChildren( IObject *, Span const &, int capacity, float xmid, float ymid );
			void insert( IObject *, Span const &, int capacity );

		};


		// methods
		QuadTree( int capacity = 8 );
		QuadTree( float xmin, float xmax, float ymin, float ymax, int capacity );
		~QuadTree();

		void insert( IObject * );
		void remove( IObject * );

		// data
		Node *root;

	private:
		void clean( Node * );
		int m_capacity;
	};
}
